SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>VEGAS algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">VEGAS algorithm</span></span>

</h1>

</header>

<p>The <b>VEGAS algorithm</b>, due to <a href="G._Peter_Lepage" title="G. Peter Lepage">G. Peter Lepage</a>,<sup id="cite_ref-Lepage1978_1-0" class="reference"><a href="#cite_note-Lepage1978-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Lepage1980_2-0" class="reference"><a href="#cite_note-Lepage1980-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Ohl1999_3-0" class="reference"><a href="#cite_note-Ohl1999-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> is a method for <a href="Variance_reduction" title="Variance reduction">reducing error</a> in <a href="Monte_Carlo_simulation" class="mw-redirect" title="Monte Carlo simulation">Monte Carlo simulations</a> by using a known or approximate <a href="Probability_distribution" title="Probability distribution">probability distribution</a> function to concentrate the search in those areas of the <a href="Integrand" class="mw-redirect" title="Integrand">integrand</a> that make the greatest contribution to the final <a href="Integral" title="Integral">integral</a>.

</p><p>The VEGAS algorithm is based on <a href="Importance_sampling" title="Importance sampling">importance sampling</a>. It samples points from the probability distribution described by the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|,}</annotation>

</semantics>

</math></span><img src="./fcd44219cf38ef71f90bd3ba8a4e2393e8df9dbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.219ex; height:2.843ex;" alt="{\displaystyle |f|,}" loading="lazy"></span> so that the points are concentrated in the regions that make the largest contribution to the integral. The <a href="GNU_Scientific_Library" title="GNU Scientific Library">GNU Scientific Library</a> (GSL) provides a VEGAS routine.

</p>

<div class="mw-heading mw-heading2"><h2 id="Sampling_method">Sampling method</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Importance_sampling" title="Importance sampling">Importance sampling</a></div>

<p>In general, if the Monte Carlo integral of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> over a volume <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math></span><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"></span> is sampled with points distributed according to a probability distribution described by the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g,}</annotation>

</semantics>

</math></span><img src="./81f2986cd965e404a1ee33ec84baee5c43da47fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.763ex; height:2.009ex;" alt="{\displaystyle g,}" loading="lazy"></span> we obtain an estimate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {E} _{g}(f;N),}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {E} _{g}(f;N),}</annotation>

</semantics>

</math></span><img src="./fe56922ad5d2dbdc15f98792c7387390fec63b31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.437ex; height:3.009ex;" alt="{\displaystyle \mathrm {E} _{g}(f;N),}" loading="lazy"></span>

</p>

<msub>

</mrow>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {E} _{g}(f;N)={1 \over N}\sum _{i}^{N}{f(x_{i})}/g(x_{i}).}</annotation>

</semantics>

</math></span><img src="./5db3626a7d471c056eefc37a028ecbf6754cfa08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:30.998ex; height:7.343ex;" alt="{\displaystyle \mathrm {E} _{g}(f;N)={1 \over N}\sum _{i}^{N}{f(x_{i})}/g(x_{i}).}" loading="lazy"></span></dd></dl>

<p>The <a href="Variance" title="Variance">variance</a> of the new estimate is then

</p>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Var} _{g}(f;N)=\mathrm {Var} (f/g;N)}</annotation>

</semantics>

</math></span><img src="./20c7750b5887e798c979e53e10ec5d6dc6658659.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.404ex; height:3.009ex;" alt="{\displaystyle \mathrm {Var} _{g}(f;N)=\mathrm {Var} (f/g;N)}" loading="lazy"></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Var} (f;N)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Var} (f;N)}</annotation>

</semantics>

</math></span><img src="./77d9840f8d57c74fa5e0ce6252f4c5cab0176ccc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.003ex; height:2.843ex;" alt="{\displaystyle \mathrm {Var} (f;N)}" loading="lazy"></span> is the variance of the original estimate, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}">

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}</annotation>

</semantics>

</math></span><img src="./acfd795197fc64ff4f331ffe95056686587b635e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.085ex; height:3.176ex;" alt="{\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}" loading="lazy"></span>

</p><p>If the probability distribution is chosen as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}">

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}</annotation>

</semantics>

</math></span><img src="./af75a92a1cc90186d4bf5cf5ebdbfb018973ff4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.496ex; height:3.176ex;" alt="{\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}" loading="lazy"></span> then it can be shown that the variance <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Var} _{g}(f;N)}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Var} _{g}(f;N)}</annotation>

</semantics>

</math></span><img src="./78202d6331d7b0e8cff13f5b8494551fc55a600d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.024ex; height:3.009ex;" alt="{\displaystyle \mathrm {Var} _{g}(f;N)}" loading="lazy"></span> vanishes, and the error in the estimate will be zero. In practice it is not possible to sample from the exact distribution g for an arbitrary function, so importance sampling algorithms aim to produce efficient approximations to the desired distribution.

</p>

<div class="mw-heading mw-heading2"><h2 id="Approximation_of_probability_distribution">Approximation of probability distribution</h2></div>

<p>The VEGAS algorithm approximates the exact distribution by making a number of passes over the integration region while <a href="Histogram" title="Histogram">histogramming</a> the function f. Each histogram is used to define a sampling distribution for the next pass. Asymptotically this procedure converges to the desired distribution. In order to avoid the number of histogram bins growing like <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K^{d}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{d}}</annotation>

</semantics>

</math></span><img src="./ba24fc3a254608fbde73fffa05104d5e3a98dea3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.186ex; height:2.676ex;" alt="{\displaystyle K^{d}}" loading="lazy"></span> with dimension <i>d</i> the probability distribution is approximated by a separable function: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }</annotation>

</semantics>

</math></span><img src="./bfa4a715b68770b3820b85c31fd2c6f484691f44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.406ex; height:2.843ex;" alt="{\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }" loading="lazy"></span> so that the number of bins required is only <i>Kd</i>. This is equivalent to locating the peaks of the function from the <a href="Projection_(mathematics)" title="Projection (mathematics)">projections</a> of the integrand onto the coordinate axes. The efficiency of VEGAS depends on the validity of this assumption. It is most efficient when the peaks of the integrand are well-localized. If an integrand can be rewritten in a form which is approximately separable this will increase the efficiency of integration with VEGAS.

</p>

<ul><li><a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas algorithm</a></li>

<li><a href="Monte_Carlo_integration" title="Monte Carlo integration">Monte Carlo integration</a></li>

<li><a href="Importance_sampling" title="Importance sampling">Importance sampling</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLepage1978" class="citation journal cs1">Lepage, G.P. (May 1978). "A New Algorithm for Adaptive Multidimensional Integration". <i>Journal of Computational Physics</i>. <b>27</b> (2): <span class="nowrap">192–</span>203. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1978JCoPh..27..192L">1978JCoPh..27..192L</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0021-9991%2878%2990004-9">10.1016/0021-9991(78)90004-9</a>.</cite></span>

</li>

<li id="cite_note-Lepage1980-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Lepage1980_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFLepage1980" class="citation journal cs1 cs1-prop-long-vol">Lepage, G.P. (March 1980). "VEGAS: An Adaptive Multi-dimensional Integration Program". <i>Cornell Preprint</i>. CLNS 80-447.</cite></span>

</li>

<li id="cite_note-Ohl1999-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Ohl1999_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFOhl1999" class="citation journal cs1">Ohl, T. (July 1999). "Vegas revisited: Adaptive Monte Carlo integration beyond factorization". <i>Computer Physics Communications</i>. <b>120</b> (1): <span class="nowrap">13–</span>19. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/hep-ph/9806432">hep-ph/9806432</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1999CoPhC.120...13O">1999CoPhC.120...13O</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0010-4655%2899%2900209-X">10.1016/S0010-4655(99)00209-X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18194240">18194240</a>.</cite></span>

</li>

</ol></div></div><p><br>

</p><p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2022-07-20" href="https://en.wikipedia.org/wiki/?title=VEGAS_algorithm&oldid=1099310946">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>